package MyPriorityQueue;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 */
public class MyPriorityQueue {
    private int size;
    private int[] elem;
    public MyPriorityQueue(){
        this.elem=new int[10];
    }

    public boolean isEmpty(){
        return size==0;
    }

    public boolean isFull(){
        return size==elem.length;
    }

    private void grow(){
        this.elem = Arrays.copyOf(elem,elem.length*2);
    }

    public void initArray(int[] array){
        for (int i = 0; i < array.length; i++) {
            if(isFull()){
                grow();
            }
            this.elem[i]=array[i];
            size++;
        }
    }
    public void creatBigHeap(){
        for (int pre = (size-1-1)/2; pre >=0 ; pre--) {
            shiftDownSmall(pre,size);
        }
    }
    private void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    public void shiftUp(int child){
        int pre =(child-1)/2;
        while (pre >= 0) {
            if(elem[pre]<elem[child]){
                swap(elem,child,pre);
                child=pre;
                pre=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public void offer(int value){
        if(isFull()){
            grow();
        }
        elem[size]=value;
        shiftUp(size);
        size++;
    }


    public  int poll(){
        if(isEmpty()){
            return -1;
        }
        int ret =elem[0];
        size--;
        swap(elem,0,size);
        shiftDown(0,size);
        return ret;
    }

    public int peek(){
        if (isEmpty()){
            return -1;
        }
        return elem[0];
    }



    public void shiftDown(int pre,int size){
        int child =pre*2+1;
          while (child<size){
          if(child+1<size&&elem[child]<elem[child+1]){
              child++;
          }
          if(elem[pre]<elem[child]){
              swap(elem,pre,child);
              pre =child;
              child =pre*2+1;
          }else {
              break;
          }
      }
    }

    public void shiftDownSmall(int pre,int size){
        int child =pre*2+1;
        while (child<size){
            if(child+1<size&&elem[child]>elem[child+1]){
                child++;
            }
            if(elem[pre]>elem[child]){
                swap(elem,pre,child);
                pre =child;
                child =pre*2+1;
            }else {
                break;
            }
        }
    }
}
